#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution{
private:
	int getDepth(TreeNode* root){
		if(root == NULL){
			return 0;
		}
		int leftDepth = getDepth(root->left);
		int rightDepth = getDepth(root->right);
		return max(leftDepth,rightDepth) + 1;
	}
public:
	int maxDepth(TreeNode* root){
		return getDepth(root);
	}
};

/**
 * 前序遍历
 */
class Solution2{
private:
	int result;
	void getDepth(TreeNode* node,int depth){
		if(node == NULL){
			return;
		}
		result = depth > result ? depth : result;
		getDepth(node->left,depth + 1);
		getDepth(node->right,depth + 1);
	}
public:
	int maxDepth(TreeNode* root){
		result = 0;
		getDepth(root,1);
		return result;
	}
};

